package com.cat.chapter035;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author cat
 * @description https://leetcode.cn/problems/all-oone-data-structure/
 * @create 2025/6/13 20:48
 * @since JDK17
 */

public class AllOne {
    Bucket head;
    Bucket tail;
    HashMap<String, Bucket> map = new HashMap<>();

    class Bucket {
        HashSet<String> set;
        int cnt;
        Bucket last;
        Bucket next;

        public Bucket(String s, int cnt) {
            this.set = new HashSet<>();
            this.cnt = cnt;
            this.set.add(s);
        }

        public void insert(Bucket bucket) {
            bucket.next = this.next;
            this.next.last = bucket;
            this.next = bucket;
            bucket.last = this;
        }

        public void remove() {
            Bucket next = this.next;
            Bucket last = this.last;
            next.last = last;
            last.next = next;
            this.last = null;
            this.next = null;
        }
    }

    public AllOne() {
        head = new Bucket("", 0);
        tail = new Bucket("", Integer.MAX_VALUE);
        head.next = tail;
        tail.last = head;
    }

    public void inc(String key) {
        if (map.containsKey(key)) { // 存在该字符串
            Bucket bucket = map.get(key);
            if (bucket.next.cnt == bucket.cnt + 1) { // 有下一个
                bucket.next.set.add(key);
            } else {
                bucket.insert(new Bucket(key, bucket.cnt + 1));
            }
            map.put(key, bucket.next);
            bucket.set.remove(key);
            if (bucket.set.isEmpty()) {
                bucket.remove();
            }
        } else {
            if (head.next.cnt == 1) {
                head.next.set.add(key);
            } else {
                head.insert(new Bucket(key, 1));
            }
            map.put(key, head.next);
        }
    }

    public void dec(String key) {
        Bucket bucket = map.get(key);
        bucket.set.remove(key);
        if (bucket.cnt - 1 == bucket.last.cnt) {
            bucket.last.set.add(key);
        } else {
            bucket.last.insert(new Bucket(key, bucket.cnt - 1));
        }
        map.put(key, bucket.last);
        if (bucket.set.isEmpty()) {
            bucket.remove();
        }
    }

    public String getMaxKey() {
        return tail.last.set.iterator().next();
    }

    public String getMinKey() {
        return head.next.set.iterator().next();
    }
}
